package bszt.jd;

import java.util.*;

public class Code03 {

    /**
     * 问题描述
     * LYA是一位年轻的魔法师，她决定进行一次跨国魔法旅行。这个魔法世界有n个城市，这些城市之间有m条单向的魔法通道。每条魔法通道都有一个固定的魔力消耗值
     * 作为一个追求完美的魔法师，LYA希望从起点城市1到达终点城市n，并且在整个旅程中恰好消耗a点魔力。她想知道有多少种不同的旅行路线可以满足这个条件
     * 你能帮助LYA计算出有多少种不同的旅行方案吗？
     * <p></p>
     * 输入格式
     * 第一行包含三个整数n、m和a，分别表示城市数量、魔法通道数量和目标魔力消耗值
     * <p></p>
     * 接下来m行，每行包含三个整数u_i、v_i和w_i，表示一条从城市u_i到城市v_i的魔法通道，使用这条通道需要消耗w_i点魔力
     * <p></p>
     * 输出格式
     * 如果旅行方案数量大于等于20220201种，请在第一行输出"Magic is everywhere!"，然后在第二行输出旅行方案数对20220201取模的结果
     * 否则，只需输出一行，表示旅行方案的总数
     */

    static final int MOD = 20220201;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int a = sc.nextInt();

        // 构建图和入度数组
        List<List<Pair>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        int[] inDegree = new int[n + 1];

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            graph.get(u).add(new Pair(v, w));
            inDegree[v]++;
        }

        // 初始化dp数组和溢出标记
        int[][] dp = new int[n + 1][a + 1];
        boolean[] overflow = new boolean[n + 1];
        dp[1][0] = 1;

        // 拓扑排序
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (Pair next : graph.get(curr)) {
                int nextCity = next.city;
                int cost = next.cost;
                inDegree[nextCity]--;
                if (inDegree[nextCity] == 0) {
                    queue.offer(nextCity);
                }

                for (int j = 0; j + cost <= a; j++) {
                    if (dp[nextCity][j + cost] + dp[curr][j] >= MOD || overflow[curr]) {
                        overflow[nextCity] = true;
                    }
                    dp[nextCity][j + cost] = (dp[nextCity][j + cost] + dp[curr][j]) % MOD;
                }
            }
        }

        // 输出结果
        if (overflow[n]) {
            System.out.println("Magic is everywhere!");
        }
        System.out.println(dp[n][a]);
    }

    static class Pair {
        int city, cost;

        Pair(int city, int cost) {
            this.city = city;
            this.cost = cost;
        }
    }
}
